package 第四周;

/*
 * @author  YxinMiracle
 * @date  2022-04-30 11:17
 * @Gitee: https://gitee.com/yxinmiracle
 */


import javafx.util.Pair;

import java.util.*;


public class 滑动窗口最大值 {

    public int[] maxSlidingWindow(int[] nums, int k) {
        int num = 0;
        List<Integer> ans = new ArrayList<>();
        int[] result;
        PriorityQueue<Pair<Integer, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Pair<Integer, Integer>>() {
            @Override
            public int compare(Pair<Integer, Integer> o1, Pair<Integer, Integer> o2) {
                return o2.getKey() - o1.getKey() ;
            }
        });
        for (int i = 0; i < nums.length; i++) {
            maxHeap.add(new Pair<>(nums[i], i));
            if (i >= k-1) {
                while (maxHeap.peek().getValue() <= i - k) maxHeap.poll();
                num ++;
                ans.add(maxHeap.peek().getKey());
            }
        }
        result = new int[num];
        for (int i = 0; i < num; i++) {
            result[i] = ans.get(i);
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new 滑动窗口最大值().maxSlidingWindow(new int[]{-7,-8,7,5,7,1,6,0},4));
    }

}
